/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        /*
        RandomListNode dummy = pHead;
        RandomListNode newHead = new RandomListNode(-1);
        RandomListNode ret = newHead;
        while (dummy != null) {
            newHead.next = new RandomListNode(dummy.label);
            dummy = dummy.next;
            newHead = newHead.next;
        }

        dummy = pHead;
        newHead = ret.next;

        Map<RandomListNode, Integer> map1 = new HashMap<>();
        Map<Integer, RandomListNode> map2 = new HashMap<>();

        int num = 0;
        while (dummy != null && newHead != null) {
            map1.put(dummy, num);
            map2.put(num, newHead);
            dummy = dummy.next;
            newHead = newHead.next;
            num++;
        }

        dummy = pHead;
        newHead = ret.next;

        while (dummy != null) {
            if (dummy.random == null) {
                newHead.random = null;
            }
            else {
                int index = map1.get(dummy.random);
                newHead.random = map2.get(index);
            }
            newHead = newHead.next;
            dummy = dummy.next;
        }

        return ret.next;
        */

        
        //空节点直接返回
        if(pHead == null)
            return pHead;
        //添加一个头部节点
        RandomListNode cur = pHead;
        //遍历原始链表，开始复制
        while(cur != null){
            //拷贝节点
            RandomListNode clone = new RandomListNode(cur.label);
            //将新节点插入到被拷贝的节点后
            clone.next = cur.next;
            cur.next = clone;
            cur = clone.next;
        }
        cur = pHead;
        RandomListNode clone = pHead.next;
        RandomListNode res = pHead.next;
        //连接新链表的random节点
        while(cur != null){
            //跟随前一个连接random
            if(cur.random == null)
                clone.random = null;
            else
                //后一个节点才是拷贝的
                clone.random = cur.random.next;
            //cur.next必定不为空
            cur = cur.next.next;
            //检查末尾节点
            if(clone.next != null)
                clone = clone.next.next;
        }
        cur = pHead;
        clone = pHead.next;
        //拆分两个链表
        while(cur != null){
            //cur.next必定不为空
            cur.next = cur.next.next;
            cur = cur.next;
            //检查末尾节点
            if(clone.next != null)
                clone.next = clone.next.next;
            clone = clone.next;
        }
        return res;
        
    }
}
